/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class FindEventualSafeStates {
	public List<Integer> eventualSafeNodes(int[][] graph) {
		Set<Integer> eventual = new HashSet<>();
		int beforeSize = 0;
		do {
			beforeSize = eventual.size();
			for (int i = 0; i < graph.length; i++) {
				if (!eventual.contains(i)) {// 对于尚未是终态的点
					boolean added = true;
					for (int integer : graph[i]) {
						if (!eventual.contains(integer)) {
							added = false;
						}
					}
					if (added) {
						eventual.add(i);
					}
				}
			}
		} while (beforeSize != eventual.size());
		List<Integer> list = new ArrayList<>(eventual);
		Collections.sort(list);
		return list;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] graph = { { 1, 2 }, { 2, 3 }, { 5 }, { 0 }, { 5 }, {}, {} };
		System.out.println(new FindEventualSafeStates().eventualSafeNodes(graph));
	}

}
